Search results for "Picture language"

TWO-DIMENSIONAL FINITE STATE RECOGNIZABILITY

1996

The purpose of this paper is to investigate about a new notion of finite state recognizability for two-dimensional (picture) languages. This notion takes as starting point the characterization of one-dimensional recognizable languages in terms of local languages and projections. Such notion can be extended in a natural way to the two-dimensional case. We first introduce a notion of local picture language and then we define,a recognizable picture language as a projection of a local picture language. The family of recognizable picture languages is denoted by REC. We study some combinatorial and language-theoretic properties of family REC. In particular we prove some closure properties with re…

Adding symbolic information to picture models: definitions and properties

2005

AbstractIn the paper we propose extensions of some picture models, such as colored, drawn and pixel pictures. Such extensions are conceived by observing that a picture may embed more information than the shape, such as colors, labels, etc., which can be represented by a symbol from an alphabet and can be associated to segments, points or pixels. New interesting issues derived from the introduction of symbols will be investigated together with some complexity and decidability questions for the proposed extensions.

Elements of Language Theory

1988

In this chapter we shall review the mathematical and computer science background on which the presentation in this book is based. We shall discuss the elements of discrete mathematics and formal language theory, emphasizing those issues that are of importance from the point of view of context-free parsing. We shall devote a considerable part of this chapter to matters such as random access machines and computational complexity. These will be relevant later when we derive efficient algorithms for parsing theoretic problems or prove lower bounds for the complexity of these problems. In this chapter we shall also discuss a general class of formal language descriptors called “rewriting systems”…

Ordinal mind change complexity of language identification

1997

The approach of ordinal mind change complexity, introduced by Freivalds and Smith, uses constructive ordinals to bound the number of mind changes made by a learning machine. This approach provides a measure of the extent to which a learning machine has to keep revising its estimate of the number of mind changes it will make before converging to a correct hypothesis for languages in the class being learned. Recently, this measure, which also suggests the difficulty of learning a class of languages, has been used to analyze the learnability of rich classes of languages. Jain and Sharma have shown that the ordinal mind change complexity for identification from positive data of languages formed…

Recognizable picture languages and polyominoes

2007

We consider the problem of recognizability of some classes of polyominoes in the theory of picture languages. In particular we focus our attention oil the problem posed by Matz of finding a non-recognizable picture language for which his technique for proving the non-recognizability of picture languages fails. We face the problem by studying the family of L-convex polyominoes and some closed families that are similar to the recognizable family of all polyominoes but result to be non-recognizable. Furthermore we prove that the family of L-convex polyominoes satisfies the necessary condition given by Matz for the recognizability and we conjecture that the family of L-convex polyominoes is non…

Ambiguity and complementation in recognizable two-dimensional languages

2008

The theory of one-dimensional (word) languages is well founded and investigated since fifties. From several years, the increasing interest for pattern recognition and image processing motivated the research on two-dimensional or picture languages, and nowadays this is a research field of great interest. A first attempt to formalize the concept of finite state recognizability for two-dimensional languages can be attributed to Blum and Hewitt ([7]) who started in 1967 the study of finite state devices that can define two-dimensional languages, with the aim to finding a counterpart of what regular languages are in one dimension. Since then, many approaches have been presented in the literature…

Implications of Theories of Language for Information Systems

1985

This article demonstrates how language views can be adopted into an information systems context. We distinguish here between five language views: denotational, generative, cognitive, behavioristic, and interactionist. These views differ in their assumptions about he origin of linguistic behavior, the primary functions of language, elements of language, and the nature of linguistic knowledge. Information system development approaches can be characterized by their underlying language views. This explains great differences in development methods and research. Thus, language views have implications and should be chosen continency for a given information system context.

Matrix-based complexity functions and recognizable picture languages

2008

Reducing Local Alphabet Size in Recognizable Picture Languages

2021

A recognizable picture language is defined as the projection of a local picture language defined by a set of two-by-two tiles, i.e. by a strictly-locally-testable (SLT) language of order 2. The family of recognizable picture languages is also defined, using larger k by k tiles, \(k>2\), by the projection of the corresponding SLT language. A basic measure of the descriptive complexity of a picture language is given by the size of the SLT alphabet using two-by-two tiles, more precisely by the so-called alphabetic ratio of sizes: SLT-alphabet/picture-alphabet. We study how the alphabetic ratio changes moving from two to larger tile sizes, and we obtain the following result: any recognizable pi…